#pragma once

#include "list.h"
#include "tools.h"
#include "addition.h"
#include "multiplication.h"

template<typename list, size_t value, size_t carry>
struct division_short_reversed
{
   typedef typename division_short_reversed<
      list_t<
         list::head_ + carry,
         typename list::tail_
      >,
      value,
      0
   >::result_ result_;
};

template<typename list, size_t value>
struct division_short_reversed<list, value, 0>
{
   typedef list_t<
      list::head_ / value,
      typename division_short_reversed<
         typename list::tail_,
         value,
         (list::head_ % value) * BASE
      >::result_
   > result_;
};

template<size_t value, size_t carry>
struct division_short_reversed<empty_list_t, value, carry>
{
   typedef empty_list_t result_;
};

template<size_t value>
struct division_short_reversed<empty_list_t, value, 0>
{
   typedef empty_list_t result_;
};

template<typename list, size_t value>
struct division_short
{
   typedef typename normalize<
      typename division_short_reversed<
         list,
         value,
         0
      >::result_
   >::result_ result_;
};

template<typename first, typename second, typename left, typename right, typename middle>
struct find_divisor
{
   typedef typename if_tool<
      ((compare_to<
         first,
         typename multiplication<
            second,
            middle
         >::result_
      >::result_) < 0),
      typename find_divisor<
         first,
         second,
         left,
         middle,
         typename division_short<
            typename addition<
               left,
               middle
            >::result_,
            2
         >::result_
      >::result_,
      typename find_divisor<
         first,
         second,
         middle,
         right,
         typename division_short<
            typename addition<
               middle,
               right
            >::result_,
            2
         >::result_
      >::result_
   >::result_ result_;
};

template<typename first, typename second, typename left, typename right>
struct find_divisor<first, second, left, right, left>
{
   typedef left result_;
};

template<typename first, typename second>
struct division_reversed
{
   typedef typename normalize<
      typename find_divisor<
         first,
         second,
         empty_list_t,
         first,
         typename division_short<
            first,
            2>::result_
      >::result_
   >::result_ result_;
};

template<typename first, typename second>
struct division
{
   typedef typename if_tool<
      length<
         typename division_reversed<
            first,
            second
         >::result_
      >::result_ == 0,
      list_t<
         0,
         empty_list_t
      >,
      typename division_reversed<
         first,
         second
      >::result_
   >::result_ result_;
};